package midsearch;

/**
 * 题目 ：寻找插入位置
 * 题目详述 ：
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。
 * 如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 */
public class SearchInsert {
    /**
     * 核心思想 ：
     * 由于题目条件必须使用时间复杂度为O（logn）的算法，所以采用二分查找，是最合适的算法；
     * 满足目标条件：
     * （1）当前位置index的数组值 <= target目标值；
     * （2）同时，也要去满足前一个位置index - 1的数组值 > target；
     * ===》 即，同时满足以上两个条件的话，即代表寻找到符合条件的插入位置；
     *
     * 特殊情况：
     * （1）即，当数组中所有元素都大于/等于target目标值的话，即需要返回 0;
     * （2）即，当数组中所有元素都小于target目标值的话，即需要返回 num.length;
     * @param nums
     * @param target
     * @return
     */
    public int searchInsert(int[] nums, int target) {
        int start = 0;
        int end = nums.length - 1;
        // 二分查找（即，在满足start <= end的情况下,不断进行二分查找，直至寻找到所要插入位置）
        while(start <= end){
            int middle = (start + end) / 2;
            // 当前遍历的数组元素值 >= 目标元素值
            // 一旦能够进入到此if语句，即代表该 num数组中存在大于/等于target值的元素
            if (nums[middle] >= target){
                // 同时满足，前一个位置的数组元素值 < 目标元素值，即寻找到所要插入元素位置
                // 考虑特殊情况：即，target <= num数组中的所有元素值（由于当前if语句是向start逐渐靠近，只对于end进行修改）
                if(middle == 0 || nums[middle - 1] < target){
                   return middle;
                }
                // 若是未满足第二个条件的话，即未能够找到所要插入元素的位置
                end = middle - 1;
            }
            // 当前遍历的数组元素值 < 目标元素值
            else {
                // 特殊情况 ：即，target > num数组中的所有元素；
                // 由于此if语句的变化在于 start = middle + 1,即由于num[middle] < target,所以需要使得start = middle + 1;
                // （if语句，会逐步地向end进行靠近，只会对于start指针的值进行修改）
                start = middle + 1;
            }
        }
        // 即，上述while循环中，while循环结束都未能返回所要插入位置，即遍历到数组中最后一个元素都未找到符合条件的；
        return nums.length;
    }
    /**
     * 分析 ：
     * 需要注意的是：使用二分查找的前提条件为 所要去遍历的数组是排序的；
     *
     * 时间复杂度 ：O（logn）
     */
}
